#include <iostream>
#include <cstdlib>
#include <ctime>
#include <limits>

namespace treap
{
	int big_rand()
	{
		std::srand(std::time(0));
		return (rand() * RAND_MAX) + rand();
	}

	int const int_max = std::numeric_limits<int>::max();
	int const maxsize = 10000;

	struct node
	{
		node() { sum = size = 0; key = int_max; }
		node(int value);
		int key, value, size;
		long long sum;
		node * child[2];

		void update()
		{
			size = child[0]->size + child[1]->size + 1;
			sum = child[0]->sum + child[1]->sum + value;
		}
	} * null = new node, memory[maxsize], * alloc = memory;

	node::node(int value) : value(value)
	{
		size = 1;
		sum = value;
		child[0] = child[1] = null;
		key = big_rand();
	}

	// treap part
	node * root;
	void init() { root = null; alloc = memory; }

	node * alloc_node(int v)
	{
		alloc->value = v;
		alloc->size = 1;
		alloc->sum = v;
		alloc->child[0] = alloc->child[1] = null;
		alloc->key = big_rand();
		return alloc++;
	}

	void rot(node *& t, bool d)
	{
		node* p = t->child[d];
		t->child[d] = p->child[!d];
		p->child[!d] = t;
		t->update();
		p->update();
		if (root == t) root = p;
		t = p;
	}

	void insert(node *& t, int x)
	{
		if (t == null) { t = alloc_node(x); return; }
		bool dir = x > t->value;
		insert(t->child[dir], x);
		if (t->child[dir]->key < t->key) rot(t, dir);
		else t->update();
	}

	void erase(node *& t, int x)
	{
		if (t == null) return;
		if (t->value == x) {
			bool dir = t->child[1]->key < t->child[0]->key;
			if (t->child[dir] == null) {
				delete t;
				t = null;
				return;
			}
			rot(t, dir);
			erase(t->child[!dir], x);
			t->update();
			return;
		}
		bool dir = x > t->value;
		erase(t->child[dir], x);
		t->update();
	}

	void kth(int kth, int & x, long long & sum)
	{
		sum = 0;
		for (node* t = root; ; ) {
			int count = t->child[0]->size;
			if (kth >= count) sum += t->child[0]->sum;
			else if (kth == count) {
				x = t->value;
				return;
			}
			if (kth > count) {
				kth -= count + 1;
				sum += t->value;
				t = t->child[1];
			} else
				t = t->child[0];
		}
	}

	void insert(int x) { insert(root, x); }
	void erase(int x) { erase(root, x); }
	int size() { return root->size; }
	long long sum() { return root->sum; }
}

int main()
{
	std::ios::sync_with_stdio(false);
	treap::init();
	treap::insert(3);
	treap::insert(1);
	treap::insert(2);
}


